def q_sort(data):
    """快速排序"""
    if len(data) <= 1:
        return data

    senti = data[0]
    l = [each for each in data[1:] if each < senti]
    r = [each for each in data[1:] if each > senti]
    return q_sort(l) + [senti] + q_sort(r)


def b_search(target, data):
    """二分查找"""
    if not data:
        return False

    middle = int(len(data)/2)
    if data[middle] == target:
        return True
    elif target > data[middle]:
        return b_search(target, data[middle+1:])
    else:
        return b_search(target, data[:middle])


def s_sort(data):
    """选择排序"""
    rst = []
    while data:
        m = max(data)
        data.remove(m)
        rst.append(m)
    return rst


"""
A-->B-->U-->P
    |       |
    v       v
    C-->D<--O
"""

data = {
    'A': ['B'],
    'B': ['U', 'C'],
    'C': ['D'],
    'U': ['P'],
    'P': ['O'],
    'O': ['D']
}


def wide_search(start, det, data):
    """宽度优先搜索"""
    search = data[start]
    searched = set()
    while search:
        b = search.pop()
        if b == det: return True
        else:
            if b not in searched:
                search.extend(data.get(b) if data.get(b) else [])
            searched.add(b)
    return False

